#leetcode题目66：加一
#难度：简单
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：模拟
#注意：如果最后一位是9，则需要进位

from typing import List
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)-1,-1,-1):
            if digits[i]!=9:
                digits[i]+=1
                return digits
            else:
                digits[i]=0
                if digits[0]==0:
                    digits.insert(0,1)
                    return digits

digits=[1,2,3] #123+1=124
#预期输出：[1,2,4]
solution=Solution()
print(solution.plusOne(digits))


digits=[4,3,2,1]
#预期输出：[4,3,2,2]
solution=Solution()
print(solution.plusOne(digits))

#主要是为了应对带9的情况，如果最后一位是9，则需要进位，如果第一位是9，则需要插入1